package leetcode;

/**
 * Created by Ghost on 2014/11/21 0021.
 */
public class Partition_List {
    public ListNode partition(ListNode head, int x) {
        if(head==null)
            return null;
        ListNode insert = head;
        ListNode preIns = null;
        ListNode cur = head;
        ListNode preCur = null;
        ListNode newHead = head;
        while (cur != null && cur.val < x) {
            preCur = cur;
            cur = cur.next;
        }
        if (cur == null) {
            return newHead;
        } else {
            insert = cur;
            preIns = preCur;
            preCur = cur;
            cur = cur.next;
        }
        boolean firstSmaller = true;

        while (cur != null) {
            if (cur.val < x) {
                ListNode tmp = cur.next;
                cur.next = insert;
                if (preIns != null) {
                    preIns.next = cur;
                    preCur.next = tmp;
                    cur = tmp;
                    preIns = preIns.next;
                } else {
                    preIns = cur;
                    cur = tmp;
                    preCur.next = cur;
                    if (firstSmaller) {
                        newHead = preIns;
                        firstSmaller = false;
                    }
                }
            } else {
                preCur = cur;
                cur = cur.next;
            }
        }
        return newHead;
    }

    public static void main(String[] args){
        Partition_List partition_list = new Partition_List();
        ListNode head = new ListNode(4);
        head.next = new ListNode(1);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(2);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(2);

        ListNode newH = partition_list.partition(head,4);

        while(newH!=null){
            System.out.print(" "+newH.val);
            newH = newH.next;
        }
    }
}
